1. Field of the Invention
The present invention relates to an encoding device, decoding device, encoding/decoding device and recording/reproducing of data including an error correcting code used for a recording/reproducing device and a communication device, and more particularly to an encoding device, decoding device, encoding/decoding device and recording/reproducing device for an error correction of a data block in which an ECC code is added.
2. Description of the Related Art
In a field of such a recording/reproducing device as a magnetic disk device, and a communication system, a data decoding technology using maximum likelihood sequence detection and an error correction technology using ECC (Error Correction Code) are widely used to improve the reliability of data reproduction when data is reproduced from low quality transmission signals and recording/reproducing signals.
RS (Reed Solomon) code is used as this ECC code. In a bit string which is output from a maximum Likelihood detection unit, an incorrect value enters in several bits because of the influence of the medium noise and the circuit noise. In ECC, a bit string having an error is corrected, and an error-corrected bit string is output. For example, in the case of a magnetic disk device, retry is required if ECC correction fails, but retry should be avoided as much as possible. So it is proposed that some candidate strings are received from a maximum likelihood detector, and whether the candidate string can be decoded with ECC is sequentially tried (e.g. Japanese Patent Application Laid-Open No. H11-330985).
FIG. 37 to FIG. 39 are diagrams depicting an error correction operation based on Reed Solomon codes, and FIG. 40 is a block diagram depicting a conventional error correction circuit using a maximum likelihood sequence.
First encoding will be described. As FIG. 37 shows, a Reed Solomon code with the number of error corrections t is generated by a generation polynomial of degree 2t. For example, if the Galois field used for encoding is GF (third power of 2), and if the number of error corrections t is “1”, then the generation polynomial of the Reed Solomon code is given by the following Expression (1), for example, using a primitive element α.
      [          Expression      ⁢                          ⁢      1        ]                                                                                            G                  ⁡                                      (                    x                    )                                                  ⁢                                                                  =                                 ⁢                                                      (                                          x                      ⁢                                                                                          -                                                                                          ⁢                      1                                        )                                    ·                                      (                                          x                      ⁢                                                                                          -                                                                                          ⁢                      α                                        )                                                                                                                          =                                ⁢                                                      x                    2                                    ⁢                                                                          +                                                                          ⁢                                                            α                      3                                        ⁢                                                                                  ⁢                    x                                    ⁢                                                                          +                                                                          ⁢                  α                                                                                          (          1          )                    
In this example, three bits of a bit string are handled as one symbol, and a parity string with the 2t (=2) symbols is added to the information string in ECC encoding. For example, in the case of encoding the information string in FIG. 37, the information strings (bit representation) “001”, “110” and “101” correspond to 1, the fifth power of α, and the fourth power of α in the Galois field representation respectively. The j-th symbol here indicates the coefficient of the term xj of the polynomial of the transmission word string. Therefore the bit string (information string) represents the polynomial x4+α5 x3+x4 x2.
As FIG. 38 shows, in ECC encoding, a polynomial represented by a bit string is divided by the generation polynomial of Expression (1), and a parity string which represents the acquired remainder polynomial α4 x+α4 is added to the bit string. Since the coefficient of the terms of degree 1 and degree 0 of x are both α4 in the remainder polynomial, a parity string shown in FIG. 37 is added, and a transmission word string comprised of five symbols is generated.
If this transmission word string is recorded on a magnetic disk and is read, for example, a receive word string, including an error, may be input to the ECC decoder, as shown in FIG. 39. This receive word string is given by the following Expression (2).[Expression 2]Y(x)=αx4+α5x3+α4x2+α4x+α4  (2)
As FIG. 40 shows, in the receive side error correction circuit, a maximum likelihood detector 20 creates a plurality of candidate data strings from the input signals according to the maximum likelihood sequence. A data storage section 31 stores a plurality of created candidate data strings. An ECC decoder 22 is comprised of a syndrome calculation section 41, an error locator polynomial calculation section 42, a chien search execution section 43 and an error value calculation section 44.
The syndrome calculation section 41 calculates a syndrome calculation expression (described later) of the data string which is input to the ECC decoder 22. The error locator polynomial calculation section 42 calculates an error locator polynomial (described later) from the syndrome polynomial. For the calculation algorithm of the error locator polynomial, the Euclid method or Berlekamp Massey method, for example, is used (e.g. E. R. Berlekamp, “Algebraic Coding Theory”, McGraw-Hill Book Co., pp. 176 to 199 and pp. 218 to 240, New York, 1968, and J. L. Massay, “Shift-register Synthesis and BCH Decoding”, IEEE Transactions on Information Theory, Vol. IT-15, pp. 122 to 127, 1969).
The chien search execution section 43 executes a chien search, and decides a position on a data string where an error exists (error position) using the above mentioned error locator polynomial. The error value calculation section 44 corrects an incorrect value at the error position to a correct value. Then a decoding judgment section 32 checks the validity of the data string after correction, which is output from the error value calculation section 44, and if not valid, the decoding judgment section 32 judges this as a correction failure, and instructs the data storage section 31 to output the next decoding candidate data string.
First the syndrome calculation section 41 calculates a syndrome polynomial for the receive word string in FIG. 39, for example, using the following Expression (3).[Expression 3]S(x)=s1+s2x s1=Y(1)s2=Y(α)  (3)
In Expression (3), a syndrome si (i=1, 2, . . . , 2t) is a value acquired by substituting the i-th root of the generation polynomial G (x) of Expression (1) in the receive word polynomial Y (x), and the syndrome polynomial S (x) is a polynomial where the syndrome si is a coefficient of the term xi-1. If no error is included in the receive word string, all of si becomes “0”.
Then the error locator polynomial calculation section 42 calculates the error locator polynomial C (x) of the following Expression (4) from the syndrome polynomial S (x) according to the Berlekamp Massey method.[Expression 4]C(x)=1+α−4x  (4)
Then using the error locator polynomial C (x) of Expression (4), the chien search execution section 43 calculates the value of C (αj) (j=0, 1, 2, 3, 4), and outputs position j where C (αj)=0 is established, as an error position. In the case of the example in FIG. 39, C (α4)=1+α−4·α4=0, so it can be detected that an error exists in the fourth symbol.
Then the error value calculation section 44 calculates a correct value of the fourth symbol based on a predetermined algorithm using the syndrome polynomial S (x) of Expression (3) and the error locator polynomial C (x) of Expression (4), and this bit string is corrected. In this case, a correct value “1” is determined and the fourth symbol in the receive word string shown in FIG. 39 is corrected from α to “1”.
In the case of a magnetic device, for example, the Reed Solomon code where the number of error corrections t=20 is used as shown in FIG. 41. In ECC encoding, 10 bits constitute one symbol, and a parity string comprised of 40 symbols is inserted before one sector of a bit string (4096 bits=410 symbols). In this case, the syndrome polynomial S (x) and the error locator polynomial C (x) are given by the following Expression (5) and (6), for example.[Expression 5]S(x)=s1+s2x+ . . . +s40x39  (5)[Expression 6]C(x)=1+x+α2x2+ . . . +α35x8  (6)
On the other hand, when a block length is long, as shown in FIG. 42, the r interleave method may be used (FIG. 42 shows an example of an r=4 interleave). In other words, a block is divided into r number of blocks, and RS codes (ECC codes) are calculated for the divided blocks using the above mentioned polynomial, and added.
In terms of error correction performance, the 1 interleave method is better than the r interleave method. In other words, as FIG. 41 shows, in the case of the one interleave method, RS codes are created for an entire one block according to the above mentioned encoding and decoding principles, so correction is for an entire one block and performance is high. In the case of the r interleave method, RS codes are created for 1/r of one block, as shown in FIG. 42, so error correction is for 1/r of one block, and therefore performance is lower than the one interleave method.
For example, if one block is 4 kbytes (=32,000 bits), 12 bits of RS code must be used for each symbol as ECC code. In other words, if one symbol consists of 10 bits, the maximal number of bits is 210−1=1023 symbols (=10230 bits), and one entire block cannot be corrected.
If one symbol consists of 12 bits, the target number of bits is 212−1=4092 symbols (49104 bits), and one entire block can be corrected. However if the number of bits in one symbol is increased, the ECC encoder, decoder and buffer increases, and the circuit scale expands several times compared with the case of the current 10 bits in one symbol.
Whereas if the current one symbol 10 bit ECC is used, one interleave configuration cannot be used, instead a four interleave configuration must be used. But in this case, the error correction performance drops compared with the one interleave configuration.